package com.arron.algorithm.leetcodetop100.二叉树;


import com.arron.algorithm.ListNode;
import com.arron.algorithm.tree.TreeNode;
import sun.security.krb5.internal.PAData;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 112. 路径总和
 *  113. 路径总和 II
 *  437. 路径总和 III
 */
public class PathSum {


    int sum;
    List<List<Integer>> res;


    //定义一个map来存从根节点到叶子节点的路径上的所有的前缀节点和中每个节点和出现的次数
    Map<Long/*前缀和*/,Integer/*出现的次数*/> prefixSumMap = new HashMap<>();


    /**
     * 112. 路径总和
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {

        if(root == null) return false;
        sum = targetSum;

        return      dfs(root,0);
    }


    public boolean dfs(TreeNode root,int val){
        if(root == null) return false;

        if (root.left ==null && root.right ==null){


            return  val + root.val== sum;
        }else {
            return dfs(root.left,root.val+val)||  dfs(root.right,root.val+val);
        }

    }

    /**
     * 113. 路径总和 II
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        res = new ArrayList<>();
        if(root == null) return res;
        sum = targetSum;
        List<Integer> path  = new ArrayList<>();
        dfs01(root,0,path);
        return res;
    }

    public void dfs01(TreeNode root,int val,   List<Integer> path){
        if(root == null) return;

        path.add(root.val);
        if (root.left ==null && root.right ==null){

            if (val + root.val== sum){
                List<Integer> pathList = new ArrayList<>();
                pathList.addAll(path);
                res.add(pathList);
            }

        }
        dfs01(root.left,root.val+val,path);
        dfs01(root.right,root.val+val,path);

        //删除掉遍历过的节点
        path.remove(path.size()-1);

    }


    /**
     * 437. 路径总和 III
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSumV3(TreeNode root, long targetSum) {

        if (root == null) {
            return 0;
        }

        //以根节点出发的所有路径和
        dfs03(root,targetSum);

        //遍历以左右子节点出发的所有路径和
        pathSumV3(root.left,targetSum);
        pathSumV3(root.right,targetSum);
        return sum;
    }


    /**
     * 437. 路径总和 III 优化时间复杂度
     *  优化时间复杂度 思路来源于  560. 和为 K 的子数组 这道题一
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSumV3_plus(TreeNode root, long targetSum) {

        if (root == null) {
            return 0;
        }

        // 初始化
        prefixSumMap.put(0L,1);

        //以根节点出发的所有路径和
        dfs03_plus(root,targetSum,0);
        return sum;
//        return dfs(root,0,targetSum);
    }


    /**
     *   官方解法
     * @param root
     * @param curr
     * @param targetSum
     * @return
     */
    public int dfs(TreeNode root, long curr, long targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;


        ret = prefixSumMap.getOrDefault(curr - targetSum, 0);
        prefixSumMap.put(curr, prefixSumMap.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left,curr, targetSum);
        ret += dfs(root.right, curr, targetSum);
        prefixSumMap.put(curr, prefixSumMap.getOrDefault(curr, 0) - 1);

        return ret;
    }


    public void dfs03(TreeNode root, long targetSum){

        if (root == null) return ;

        if (root.val == targetSum){
            sum++;
        }

        dfs03(root.left,targetSum-root.val);
        dfs03(root.right,targetSum-root.val);

    }

    public void dfs03_plus(TreeNode root, long targetSum,long curSum){

        if (root == null) return ;


        curSum = curSum + root.val;



        if ( prefixSumMap.getOrDefault(curSum - targetSum,0) >0){
            sum =  sum+prefixSumMap.getOrDefault(curSum - targetSum,0);
        }
        prefixSumMap.put(curSum,prefixSumMap.getOrDefault(curSum,0)+1);

        dfs03_plus(root.left,targetSum,curSum);
        dfs03_plus(root.right,targetSum,curSum);

        //遍历过的剔除
        prefixSumMap.put(curSum,prefixSumMap.get(curSum) -1);

    }


    public static void main(String[] args)
    {

        PathSum pathSum = new PathSum();
        BuildTree buildTree = new BuildTree();
        TreeNode root = buildTree.buildTree();


        System.out.println(pathSum.pathSumV3_plus(root, 7));

    }


}
